package LC;

/**
 * https://leetcode.com/problems/majority-element/description/
 * Given an array of size n, find the majority element.
 * The majority element is the element that appears more than ⌊ n/2 ⌋ times.
 * You may assume that the array is non-empty and the majority element always exist in the array.
 * Credits:
 * Special thanks to @ts for adding this problem and creating all test cases.
 */
public class LC_169_MajorityElement_Array {
    public static void main(String[] args) {
        System.out.println(Solution.majorityElement(new int[]{1, 2, 2, 2, 3, 4, 4, 4, 4, 4}));
    }

    static class Solution {
        static int majorityElement(int[] num) {
            if (num.length < 3) return num[0];
            int majority = num[0];
            int count = 1;
            for (int i = 1; i < num.length; ++i) {
                if (count == 0) {
                    majority = num[i];
                    ++count;
                } else if (num[i] == majority)
                    ++count;
                else
                    --count;
            }
            return majority;
        }
    }
}